package cn.bellychang.leetcode.question215;

/**
 * @author ChangLiang
 * @date 2021/2/3
 */
public class Solution2 {

    /**
     * 使用非递归 循环方式实现
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {

        int index = nums.length - k;

        int beginIndex = 0;
        int endIndex = nums.length - 1;

        int partitionIndex = partition(beginIndex, endIndex, nums);
        // 循环不变量
        while (index != partitionIndex) {
            if (index > partitionIndex) {
                beginIndex = partitionIndex + 1;
                partitionIndex = partition(beginIndex, endIndex, nums);
            } else {
                endIndex = partitionIndex - 1;
                partitionIndex = partition(beginIndex,endIndex, nums);
            }
        }
        return nums[index];
    }

    public int partition(int beginIndex, int endIndex, int[] nums){

        int pivot = nums[beginIndex];
        int i = beginIndex + 1;
        int j = beginIndex + 1;
        // loop invariant: [beginIndex+1, i-1] < pivot, 剩余其他部分
        while (j <= endIndex) {
            if (nums[j] < pivot) {
                if (i != j) {
                    swap(i, j, nums);
                }
                i++;
            }
            j++;
        }
        swap(beginIndex, i-1, nums);
        return i-1;
    }

    private void swap(int i, int j, int[] nums) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
